We carry out some of Galois' work in the setting of an arbitrary first-order theory T. We replace the ambient algebraically closed field by a large model M of T, replace fields by definably closed subsets of M, assume that T codes finite sets, and obtain the fundamental duality of Galois theory matching subgroups of the Galois group of L over F with intermediate extensions F ≤ K ≤ L. This exposition of a special case of [10] has the advantage (...) of requiring almost no background beyond familiarity with fields, polynomials, first-order formulae, and automorphisms. (shrink)

This paper began as a generalization of a part of the author's PhD thesis about ACFA and ended up with a characterization of groups definable in T A . The thesis concerns minimal formulae of the form x ∈ A ∧ σ(x) = f(x) for an algebraic curve A and a dominant rational function f: A → σ(A). These are shown to be uniform in the Zilber trichotomy, and the pairs (A, f) that fall into each of the three cases (...) are characterized. These characterizations are definable in families. This paper covers approximately half of the thesis, namely those parts of it which can be made purely model-theoretic by moving from ACFA, the model companion of the class of algebraically closed fields with an endomorphism, to T A , the model companion of the class of models of an arbitrary totally-transcendental theory T with an injective endomorphism, if this model-companion exists. A T A analog of the characterization of groups definable in ACFA is obtained in the process. The full characterization of the cases of the Zilber trichotomy in the thesis is obtained from these intermediate results with heavy use of algebraic geometry. (shrink)

Simpson introduced the lattice of Π0 1 classes under Medvedev reducibility. Questions regarding completeness in are related to questions about measure and randomness. We present a solution to a question of Simpson about Medvedev degrees of Π0 1 classes of positive measure that was independently solved by Simpson and Slaman. We then proceed to discuss connections to constructive logic. In particular we show that the dual of does not allow an implication operator (i.e. that is not a Heyting (...) algebra). We also discuss properties of the class of PA-complete sets that are relevant in this context. (shrink)

We show that there is a computable procedure which, given an ∀∃-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$.

We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.

We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.

We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size $2^{2^{\aleph }0}$ , the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size $2^{2^{\aleph }0}$ , and in fact these big chains occur in every infinite interval. We (...) also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice. (shrink)

We define a variant of the standard Kripke semantics for intuitionistic logic, motivated by the connection between constructive logic and the Medvedev lattice. We show that while the new semantics is still complete, it gives a simple and direct correspondence between Kripke models and algebraic structures such as factors of the Medvedev lattice.

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the (...) sublattice of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space. (shrink)

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by (...) Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

We study a class of formulas generalizing the weak law of the excluded middle and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We use these formulas to separate logics corresponding to factors of the Medvedev lattice.

Zhores Medvedev and Mark Popovsky have both drawn attention to the positive response on the part of the scientific community to the early work of Lysenko on the phasic development of plants. This aspect of the Lysenko Affair is explored more fully in this paper. Vavilov's sponsorship of Lysenko is set in the intellectual context of plant physiology circa 1930, and in the political climate of the pressing needs of Russian agriculture at that time. Lysenko's rise was also (...) favoured by the Marxist philosophy of science then current in which the traditional distinction between basic and applied science was discarded and an opposition between proletarian and bourgeois science introduced. It is claimed that an understanding of the intellectual history must lie at the core of a social history of the Lysenko Affair if it is to prove adequate. (shrink)

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document} be the lattice of degrees of non-empty \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi_1^0}$$\end{document} subsets of 2ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document}. Cenzer and Hinman proved that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document} (...) is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{U} < _s \mathcal{V}}$$\end{document}, we can lattice embed FD(ω) into \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document} strictly between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${deg_s(\mathcal{U})}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${deg_s({\mathcal V})}$$\end{document}. We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph (...) G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

A propósito del libro de Roy A. Medvedev y Zhores A. Medvedev, El Stalin desconocido, Planeta de Agostini, Barcelona 2006, traducido por Javier Alfaya y Javier Alfaya McShane.

We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty.

This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices (...) have decidible ∃-theories. (shrink)

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

While every endpointed interval I in a linear order J is, considered as a linear order in its own right, trivially Muchnik‐reducible to J itself, this fails for Medvedev‐reductions. We construct an extreme example of this: a linear order in which no endpointed interval is Medvedev‐reducible to any other, even allowing parameters, except when the two intervals have finite difference. We also construct a scattered linear order which has many endpointed intervals Medvedev‐incomparable to itself; the only other (...) known construction of such a linear order yields an ordinal of extremely high complexity, whereas this construction produces a low‐level‐arithmetic example. Additionally, the constructions here are “coarse” in the sense that they lift to other uniform reducibility notions in place of Medvedev reducibility itself. (shrink)

The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

We characterize the join-irreducible Medvedev degrees as the degrees of complements of Turing ideals, thereby solving a problem posed by Sorbi. We use this characterization to prove that there are Medvedev degrees above the second-least degree that do not bound any join-irreducible degrees above this second-least degree. This solves a problem posed by Sorbi and Terwijn. Finally, we prove that the filter generated by the degrees of closed sets is not prime. This solves a problem posed by Bianchini (...) and Sorbi. (shrink)

Medvedev's intermediate logic (MV) can be defined by means of Kripke semantics as the family of Kripke frames given by finite Boolean algebras without units as partially ordered sets. The aim of this paper is to present a proof of the theorem: For every set of connectives such that the-fragment ofMV equals the fragment of intuitionistic logic. The final part of the paper brings the negative solution to the problem set forth by T. Hosoi and H. Ono, namely: is (...) an intermediate logic based on the axiom (abc) (ab)(a c) separable? (shrink)

Abstract.The partial ordering of Medvedev reducibility restricted to the family of Π01 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π01 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

A $\Pi^0_1$ class can be defined as the set of infinite paths through a computable tree. For classes $P$ and $Q$, say that $P$ is Medvedev reducible to $Q$, $P \leq_M Q$, if there is a computably continuous functional mapping $Q$ into $P$. Let $\mathcal{L}_M$ be the lattice of degrees formed by $\Pi^0_1$ subclasses of $2^\omega$ under the Medvedev reducibility. In "Non-branching degrees in the Medvedev lattice of $\Pi \sp{0}\sb{1} classes," I provided a characterization of nonbranching/branching and (...) a classification of the nonbranching degrees. In this paper, I present a similar classification of the branching degrees. In particular, $P$ is separable if there is a clopen set $C$ such that $P \cap C \neq \emptyset \neq P \cap C^c$ and $P \cap C \perp_M P \cap C^c$. By the results in the first paper, separability is an invariant of a Medvedev degree and a degree is branching if and only if it contains a separable member. Further define $P$ to be hyperseparable if, for all such $C$, $P \cap C \perp_M P \cap C^c$ and totally separable if, for all $X,Y \in P$, $X \perp_T Y$. I will show that totally separable implies hyperseparable implies separable and that the reverse implications do not hold, that is, that these are three distinct types of branching degrees. Along the way I will show some related results and present a combinatorial framework for constructing $\Pi^0_1$ classes with priority arguments. (shrink)

Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic. However, her factor is unnatural in the sense that it is constructed in an ad hoc manner. We present a more natural example of such a factor. We also show that the theory of every non-trivial factor of the Medvedev lattice is contained in Jankov’s logic, the deductive closure of IPC plus the weak law of the excluded middle ¬p∨¬¬p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} (...) \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\neg p \vee \neg \neg p}$$\end{document}. This answers a question by Sorbi and Terwijn. (shrink)

Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A well-known example from the literature on intuitionistic logic is the class of Medvedev frames $\langle W,R\rangle$ where $W$ is the set of nonempty subsets of some nonempty finite set $S$, and $xRy$ iff $x\supseteq y$, or more liberally, where $\langle (...) W,R\rangle$ is isomorphic as a directed graph to $\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle$. Prucnal [32] proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those $y$ such that $x\not= y$), or a complement modality (for quantifying over those $y$ such that $x\not\supseteq y$). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable---which would answer the open question of whether Medvedev's [31] "logic of finite problems'' is decidable---or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frame-incomplete logics. (shrink)

Incessantly cited by critics, Bakhtin's work none the less remains relatively unavailable: partly through lack of suitable editions, partly because no individual text conveys all the key concepts or arguments. This anthology provides in a convenient format a good selection of the writing by Bakhtin and of that attributed to Voloshinov and Medvedev. It introduces readers to the aspects most relevant to literary and cultural studies and gives a focused sense of Bakhtin's central ideas and the underlying cohesiveness of (...) his thinking. (shrink)

The article, based on archival data, as well as preserved testimonies of students, attempts to reconstruct the pedagogical views of M. E. Medvedev and A.M. Paskhalova, whose teaching activity was the basis for the subsequent formation of the vocal and pedagogical traditions of the Saratov Conservatory. The object of research here is the vocal and pedagogical traditions of the Saratov Conservatory, the subject is the pedagogical views of the professors of the initial period of activity of the educational institution (...) under consideration - M. E. Medvedev and A.M. Paskhalova. The paper analyzes the book of the student M. E. Medvedev baritone S. Y. Levik "Notes of an opera singer", as well as the methodological work of A.M. Paskhalova "Work on the production of voice for the leaders of the Russian folk song choir". It is revealed that, despite the differences in some aspects of the vocalist's voice production (soundless exercises, scientific foundations of vocalist education, the use of vocalizations, etc.), the activities of M. E. Medvedev and A. M. Paskhalova is characterized by the following general provisions: a rather low type of breathing, increased attention to the development of a sense of sound support, a cautious attitude to the development of a full range of voice, the development of clear diction, evenness of sound studies, smoothness of register transitions; soft sound attack; the ability to vocalize various dynamic gradations of vocalization qualitatively; the use of a "concentric" teaching method in the pedagogical process, increased attention to the upbringing of the emotional and dramatic component of the performer's personality. The analysis also showed that the features distinguishing the pedagogical views of professors of the initial period of the Saratov Conservatory's activity can be attributed to the use of the repertoire of Russian composers in classroom work at the initial stage of training singers. (shrink)

A $\Pi _{1}^{0}$ class is the set of paths through a computable tree. Given classes P and Q, P is Medvedev reducible to Q, P ≤M Q, if there is a computably continuous functional mapping Q into P. We look at the lattice formed by $\Pi _{1}^{0}$ subclasses of 2ω under this reduction. It is known that the degree of a splitting class of c.e. sets is non-branching. We further characterize non-branching degrees, providing two additional properties which guarantee non-branching: (...) inseparable and hyperinseparable. Our main result is to show that non-branching iff inseparable if hyperinseparable if homogeneous and that all unstated implications do not hold. We also show that inseparable and not hyperinseparable degrees are downward dense. (shrink)

Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic, using the notion of a first-order hyperdoctrine from categorical logic, to a structure which we will (...) call the hyperdoctrine of mass problems. We study the intermediate logic that the hyperdoctrine of mass problems gives us, and we study the theories of subintervals of the hyperdoctrine of mass problems in an attempt to obtain an analogue of Skvortsova’s result that there is a factor of the Medvedev lattice characterising intuitionistic propositional logic. Finally, we consider Heyting arithmetic in the hyperdoctrine of mass problems and prove an analogue of Tennenbaum’s theorem on computable models of arithmetic. (shrink)

This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

Intermediate prepositional logics we consider here describe the setI() of regular informational types introduced by Yu. T. Medvedev [7]. He showed thatI() is a Heyting algebra. This algebra gives rise to the logic of infinite problems from [13] denoted here asLM 1. Some other definitions of negation inI() lead to logicsLM n (n ). We study inclusions between these and other systems, proveLM n to be non-finitely axiomatizable (n ) and recursively axiomatizable (n ). We also show that formulas (...) in one variable do not separateLM from Heyting's logicH, andLM n (n ) from Scott's logic (H+S). (shrink)